\chapter{Section II: 关于函数}

\section{Part I: 作为程序员，先做啥，后做啥}
一份关于递归函数和Haskell的编程笔记：

关注一下这里的fib / fibGen例子：

\begin{verbatim}
fib :: Int -> Int
fib n = fibGen 0 1 n

fibGen :: Int -> Int -> Int -> Int
fibGen a b n = case n of
    0 -> a
    n -> fibGen b (a + b) (n - 1)
\end{verbatim}

我首先写下fib的类型，然后是fibGen的类型和定义，最后是fib的定义。

对于你们之中那些不习惯于编写递归函数的人来说，Haskell编程往往需要递归函数。递归函数通常需要一些辅助函数，这些辅助函数要么用来构成递归主要操作的结构，要么执行一个保持主递归函数清晰的简单任务。无论哪种情况，辅助函数都可以在包含结束条件的主递归操作定义后再实现。通常在编程时，将注意力集中在最关键的那部分代码上是一个很好的思路，而Haskell的设计更加增强了这种思路的说服力。辅助函数的定义，例如如像fib调用fibGen并传递参数'0 1 n'这种"启动"程序，可以在函数本身被定义完后再考虑。即使在一开始就知道了fib的类型，我们也应该这么做。同样地，使用Haskell可以很快实现出类似上面那种不重要函数，这样在我们考虑整体时，它们通常可以被忽略。这很可能改变你编码的方式，这可能是一种更好的方式。

\section{Part II: Functions, But Really a Sidetrack to Types}

我们继续前进，另一半是关于Haskell的通常用法，而这一半是关于函数的内容。

什么是函数？As this tutorial's alignment indicates，我们将用C/C++与Haskell作比较。在C语言中，函数是一组命令序列，这些命令都具有自己的名字空间。函数在程序执行时被调用并接受传入的参数，函数继承了其实现所在范围的名字空间，并给其调用者返回一个结果。Haskell中函数与此大体相同，当然除了一点：Haskell的函数不是一组事件序列，而是由表达式和定义组成。C和Haskell有一个很大的不同，然而，这个不同主要集中在函数具有的灵活性。在C中，函数接受参数，返回单一的返回值。我们已经看到了Haskell和其他一些语言类似，有很多种将多个值聚合到一起的方法。

两个最常见的聚合值的方法是列表和元组，并且它们可以做为函数返回值的类型。总之，Haskell中的列表长度是变长的，其所有元素类型相同；元组则是定长的且其组成元素可以类型不同。下面是一个返回元组类型的函数的例子：

\begin{verbatim}
splitAt :: Int -> [a] -> ([a], [a])
\end{verbatim}

'splitAt'接受一个Int型参数和一个列表，并返回一个元组。元组左边的列表由输入列表的前n个元素构成，其中n是该函数的第一个参数，其余元素则构成了元组中右边的那个列表。splitAt是Prelude标准库中的一个函数，关于它的具体描述可参见：

\href{http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#17}{Prelude, Section: Sublists}

我们已经看到过在一个类型定义中的列表了：

\begin{verbatim}
fibs :: [Int]
\end{verbatim}

由于fibonacci数增长迅速，但'Int'却只是一个32位的整数类型，所以最好使用'Integer'类型，它是Haskell内置的无穷精度整数类型。

\begin{verbatim}
fibs :: [Integer]
\end{verbatim}

这是个函数类型。它没有参数，返回一个整数列表。这不是什么Haskell的语法技巧，'fibs'确实是一个函数，当对其求值时，它将返回一个由fibonacci数组成的序列。这种逻辑是为了让Haskell编译器编译出的指令运行的更快，同时也有助于Haskell程序员更高效的编写代码。

\section{Part III: More Types, Because Haskell Is 'Polymorphic'}

It's time for a brief [not so brief] digression about types. As you've noticed, the trend seems to be to call everything a 'function'. And that's true. Take '4' for example. When you use a number '4' hardcoded into your code, it looks to you like the number 4. But what is it to Haskell? Type ':t 4' into Hugs or GHCi. What do you get? You get some weird junk:

\begin{verbatim}
4 :: Num a => a
\end{verbatim}

That looks like it's a function that's taking a parameter. It's not, and the key is the '=>' arrow rather than the '->' arrow. The type given is read: "four is of type 'a', where 'a' is in the class 'Num'." What's the class Num? Well, it's the class that all numbers belong to. The real answer is that Haskell has something C doesn't: true polymorphism. Most C++ programmers are familiar with the term 'overloading', which means that a function is defined for more than one set of parameter types. For instance, addition and multiplication in C/C++ are overloaded, allowing the following combinations to occur:

\begin{verbatim}
int a = 4, b = 5;
float x = 2.5, y = 7.0;
    
cout << a + b;  //9
cout << a + y;  //11
cout << y + a;  //11.0
cout << x + y;  //9.5
cout << b * a;  //20
cout << b * x;  //12.5
cout << y * b;  //35.0
cout << x * y;  //17.5
\end{verbatim}

In C/C++, this is accomplished by defining all of the following overloaded definitions for '+' and '*':

\begin{verbatim}
operator+ (int, int);
operator+ (int, float);
operator+ (float, int);
operator+ (float, float);
operator* (int, int);
operator* (int, float);
operator* (float, int);
operator* (float, float);
\end{verbatim}

The C compiler picks the appropriate type at compile time. The key here is that, in C/C++, each combination must be written separately. Also, in C/C++, any other function that uses either an int or a float must specify which one it expects, or must \_itself\_ be overloaded. This bring us to the idea of classes. For what types is '+' defined? In C/C++ it is possible to overload the operator for new types, but those new types will not be interchangeable with ints, floats, or other numeric types. For instance, sort functions such as mergeSort and quickSort would need to be rewritten to sort arrays of the new value. In constrast, here is the type of mergeSort in Haskell:

\begin{verbatim}
mergeSort :: Ord a => [a] -> [a]
\end{verbatim}

What is going on? Again, there are two parameters, not three. The first thing that appears to be a parameter is actually a class restriction. 'mergeSort', as you would expect, takes a list of objects of some type (type 'a'), and returns a list of objects of the same type. So why is the following type not sufficient?:

\begin{verbatim}
mergeSortBadType :: [a] -> [a]
\end{verbatim}

The reason is that at some point in mergeSort the items in the list will need to be compared to each other using a comparator such as '>', '<', '>=', or '<='. In Haskell, those operators are part of a class definition. The only values for which '>' and so on are defined are those which are members of class 'Ord', so named because an 'order' can be determined for them. Many numeric types are of type Ord, as are characters and strings. So mergeSort must clarify its type by stating that its parameter must be a list of objects for which '<' and so on are defined. It would also be okay to make the type more specific, but this is not necessary and generally bad technique.

And what about '4'? How come four is of type 'a', where 'a' is a member of class 'Num'? Can't it just be a Num? Or an Int? It can be an Int if we specifically say it is, like so:

\begin{verbatim}
a = (4 :: Int) + 2
\end{verbatim}

Here '4' is an Int. That is how you specify the type of something inside of an expression. But without that, 4 is of type 'a', where 'a' is in class 'Num', or more simply, 4 is of type 'a' in class 'Num'. And that is important, because '+' is defined for all member types of class Num, meaning that '4' is definitely a legal parameter for this function:

\begin{verbatim}
doubleIt :: Num a => a -> a
doubleIt n = n + n
\end{verbatim}

'-' and '*' are also defined for all member types of Num, so 4 is also allowed for this function:

\begin{verbatim}
fib :: Num a, Num b => a -> b
fib n = fibGen 0 1 n

fibGen :: Num a, Num b => b -> b -> a -> b
fibGen a b n = case n of
    0 -> a
    n -> fibGen b (a + b) (n - 1)
\end{verbatim}

That is our first Haskell fib function, but with the types changed. The first type is read, "fib is of type 'a' to 'b', where 'a' is a member of class Num and 'b' is a member of class Num." There is only one '=>' arrow because there is only ever one section of the type that describes class restrictions. Why would we do this? Shouldn't we pick a type? Well, what if you worked on a group project, and two people need to calculate fibonacci numbers? And for reasons of their own, one needed an Int returned and the other needed an Integer? Or a Double? Would you write the code twice with different types? If you were using C you would. Picking the most general types allows code reuse. Class definitions allow code reuse.

Also notice that in the initial call to 'fibGen', the third parameter is 'n', the first parameter of 'fib', and that the types of 'fib' and 'fibGen' seem to make note of this. The reason I wrote 'fib' with a different return type from its parameter is that the following would be common:

\begin{verbatim}
fib :: Int -> Integer
\end{verbatim}

We only need Int-sized storage of our counter variable, but we may need Integer-sized storage of the result. So, two separate types. Also notice how types flow in 'fibGen'. The math does not mix parameters of type 'a' and 'b', and a parameter of type 'b' is also used as the final return value. The types match not only externally but internally. Following types in this manner will be important for debugging.

Continuing onward, in the fib example we used 'tail'. Here is its type:

\begin{verbatim}
tail :: [a] -> [a]
\end{verbatim}

In C, tail would have to be reimplemented for every type of list you used. That sounds slightly contrived, so what about '!!', the index operator? Well, in most other languages, indexing a list is builtin, because it has to work for every kind. And so on. Everything in C is either overloaded, built in, or works for only one type. Well, there are a few exceptions, generally involving casting to or from '(void *)'. The point is, you're going to see 'Num a =>' at the beginning of type signatures, as well as 'a' and 'b' inside type signatures. 'a' and 'b' are type variables in this case, used by the compiler solely to determine proper types for compilation. Occassionally you will get messages such as 'can't determine type', or 'type mismatch'. The second means the you've done something wrong, but the first usually means that a type variable can't be pinned down to a single type for a function that you've written. This can happen for the simplest of reasons:

\begin{verbatim}
main = putStrLn (show 4)
\end{verbatim}

'putStrLn' takes a string and puts it on the screen. 4 has a 'polymorphic' type, i.e. it is a member of a type class, not defined as a specific type. 'show' takes anything that can be turned into a string (basically), and so it doesn't specify a type for '4' either. This leaves the compiler in a quandry, because no specific type is indicated anywhere, and it will complain. To resolve it, add the type definition like so:

\begin{verbatim}
main = putStrLn (show (4 :: Int))
\end{verbatim}

Or Integer, or Double, or whatever. This will be handy when you try to test generalized functions, and you'll need it in a few other weird cases as well.

One last note, you can define the type of multiple functions simultaneously:

\begin{verbatim}
addOne, subtractOne :: Int -> Int
\end{verbatim}

This can be handy.

\section{Part IV: Functions Already}

But we were talking about functions. As you may have noticed, it seems like anything can work as a parameter or return value for a function. This is absolutely true, as long as the types match. For instance, let's take a look at the extremely useful 'map' function:

\begin{verbatim}
map :: (a -> b) -> [a] -> [b]
\end{verbatim}

By now you can probably read that, strange as it may be. "map is of type function a to b followed by a list of type a and returns a list of type b". It's taking a function as a parameter. Not only that, but a polymorphic function, with no type restrictions. And look at the other two items. The function it takes is from a to b, and then it takes a list of type a and returns a list of type b. With a name like 'map', it's pretty clear what should happen when you use it:

\begin{verbatim}
fooList :: [Int]
fooList = [3, 1, 5, 4]
    
bar :: Int -> Int
bar n = n - 2
    
map bar fooList
= [1, -1, 3, 2]
\end{verbatim}

Nothing to it. Notice I had to give at least 'fooList' or 'bar' a specific type, or Hugs and GHC would complain that the types could not be fully determined.

You can write functions which take functions as parameters. This can be fun, and also very useful. Now let's try something stranger:

\begin{verbatim}
subEachFromTen :: [Int] -> [Int]
subEachFromTen = map (10 -)
\end{verbatim}

What the heck? First, there is absolutely supposed to be parentheses around the '-' and the '10'. Second, what does this do? Again, one step at a time. '(10 -)' is a function. It takes a number and returns ten minus that number. Use ':t' in Hugs or GHCi to find this out:

\begin{verbatim}
(10 -) :: Int -> Int
or rather

(10 -) :: Num a => a -> a
\end{verbatim}

Second, 'map' takes a function as its first parameter. There's a reason that Haskell uses arrows to define types, rather than a parenthesized list. 'map', applied to '(10 -)' has the following type (again, check in Hugs and GHCi):

\begin{verbatim}
map (10 -) :: Num a => [a] -> [a]
\end{verbatim}

It takes a list of Num members (all the same type of Num members, mind you) and returns a list of the same type (again, the same type member of Num). This is called 'partial evaluation'. You take a function, give it some of its parameters, and you've got a function that takes the rest of the parameters. You can even name this 'in-between' state, since it is just a function like anything else. So, here is 'subEachFromTen' in action:

\begin{verbatim}
subEachFromTen [4, 6, 7, 11]
= [6, 4, 3, -1]
\end{verbatim}

It does what you think it should, given how I named it. Remember that applying subEachFromTen to a list, even a named list, does not change that list, but merely returns the result.

Take some time now to play around with partial evaluation, in addition to the list functions mentioned before and list comprehensions. Remember that functions grab their parameters 'eagerly', so you have to put parentheses around any parameters that are composed of a function with its own parameters.

